{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #买卖芯片的最佳时机"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: bestTiming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #买卖芯片的最佳时机"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>数组 <code>prices</code> 记录了某芯片近期的交易价格，其中 <code>prices[i]</code> 表示的 <code>i</code> 天该芯片的价格。你只能选择 <strong>某一天</strong> 买入芯片，并选择在 <strong>未来的某一个不同的日子</strong> 卖出该芯片。请设计一个算法计算并返回你从这笔交易中能获取的最大利润。</p>\n",
    "\n",
    "<p>如果你不能获取任何利润，返回 0。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>prices = [3, 6, 2, 9, 8, 5]\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>在第 3 天（芯片价格 = 2）买入，在第 4 天（芯片价格 = 9）卖出，最大利润 = 9 - 2 = 7。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>prices = [8, 12, 15, 7, 3, 10]\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>在第 5 天（芯片价格 = 3）买入，在第 6 天（芯片价格 = 10）卖出，最大利润 = 10 - 3 = 7。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>提示：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= prices.length &lt;= 10^5</code></li>\n",
    "\t<li><code>0 &lt;= prices[i] &lt;= 10^4</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意：</strong>本题与主站 121 题相同：<a href=\"https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/\">https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/</a></p>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [gu-piao-de-zui-da-li-run-lcof](https://leetcode.cn/problems/gu-piao-de-zui-da-li-run-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [gu-piao-de-zui-da-li-run-lcof](https://leetcode.cn/problems/gu-piao-de-zui-da-li-run-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,6,2,9,8,5]', '[8,12,15,7,3,10]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "        if not prices:\n",
    "            return 0\n",
    "        pre = cur = prices[0]\n",
    "        ans = 0\n",
    "        for price in prices:\n",
    "            if price > cur:\n",
    "                cur = price\n",
    "                ans = max(price - pre, ans)\n",
    "            elif price < pre:\n",
    "                pre = cur = price\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "        if not prices:\n",
    "            return 0\n",
    "        max_profit = 0\n",
    "        min_price = float(\"inf\")\n",
    "        for price in prices:\n",
    "            max_profit = max(max_profit, price - min_price)\n",
    "            min_price = min(min_price, price)\n",
    "        return max_profit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "        if not prices:\n",
    "            return 0\n",
    "        minPrice = prices[0]\n",
    "        res = 0\n",
    "        maxx = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            minPrice = min(minPrice, prices[i])\n",
    "            if prices[i] - minPrice > maxx:\n",
    "                res = i\n",
    "                maxx = prices[i] - minPrice\n",
    "        return maxx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "        ans = 0\n",
    "        min_prices = 100000\n",
    "        max_prices = -1\n",
    "        for i in range(len(prices)):\n",
    "            if prices[i] < min_prices:\n",
    "                ans = max(ans, -min_prices+max_prices)\n",
    "                min_prices = prices[i]\n",
    "                max_prices = -1\n",
    "            elif prices[i] > max_prices :\n",
    "                max_prices = prices[i]\n",
    "                ans = max(ans, -min_prices+max_prices)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "        min_price = inf\n",
    "        max_profit = 0\n",
    "        for p in prices:\n",
    "            min_price = min(min_price, p)\n",
    "            max_profit = max(max_profit, p-min_price)\n",
    "        return max_profit\n",
    "\n",
    "\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "        cost, profit = float(\"+inf\"), 0\n",
    "        for price in prices:\n",
    "            cost = min(cost, price)\n",
    "            profit = max(profit, price - cost)\n",
    "        return profit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        min_price = float('inf')\n",
    "        max_profit = 0\n",
    "        for i in range(n):\n",
    "            max_profit = max(max_profit, prices[i]-min_price)\n",
    "            min_price = min(min_price, prices[i])\n",
    "        return max_profit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "        max_profit, low_price = 0, float(\"inf\")\n",
    "        for price in prices:\n",
    "            low_price = min(low_price, price)\n",
    "            max_profit = max(max_profit, price - low_price)\n",
    "        return max_profit\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "        cost = float(\"+inf\")\n",
    "        profit = 0\n",
    "        for p in prices:\n",
    "            cost = min(cost, p)\n",
    "            profit = max(profit, p - cost)\n",
    "        \n",
    "        return profit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "        min_price, max_profit = inf,0         \n",
    "        for p in prices:\n",
    "            min_price = min(min_price, p)\n",
    "            max_profit = max(max_profit, p-min_price)\n",
    "        return max_profit\n",
    "\n",
    "\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "        if prices == []: return 0\n",
    "        max_profit = 0\n",
    "        min_price = prices[0]\n",
    "        \n",
    "        for price in prices:\n",
    "            min_price = min(min_price, price)\n",
    "            max_profit = max(max_profit, price - min_price)\n",
    "            \n",
    "        return max_profit\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "        min_price, max_profit = inf,0         \n",
    "        for p in prices:\n",
    "            min_price = min(min_price, p)\n",
    "            max_profit = max(max_profit, p-min_price)\n",
    "        return max_profit\n",
    "\n",
    "\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "        if not prices: return 0\n",
    "        res = 0\n",
    "        tmp = prices[0]\n",
    "        for i in range(1, len(prices)):\n",
    "            res = max(prices[i]-tmp, res)\n",
    "            tmp = min(tmp, prices[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "        if not prices:\n",
    "            return 0\n",
    "        dp=[0]*len(prices)\n",
    "        for i in range(1,len(dp)):\n",
    "            if prices[i]>=min(prices[:i]):\n",
    "                dp[i]=prices[i]-min(prices[:i])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "        if len(prices)<=1:\n",
    "            return 0\n",
    "        dp=[0]\n",
    "        num=prices[0]\n",
    "        m=0\n",
    "        for i in range(1,len(prices)):\n",
    "            dp.append(max(dp[i-1],prices[i]-num))\n",
    "            if prices[i]<num:\n",
    "                num=prices[i]\n",
    "            if dp[i]>m:\n",
    "                m=dp[i]\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        dp = [0] * n\n",
    "        dp[0] = prices[0]\n",
    "        m = 0\n",
    "        for i in range(1, n):\n",
    "            if prices[i] < dp[i - 1]:\n",
    "                dp[i] = prices[i]\n",
    "            else:\n",
    "                dp[i] = dp[i - 1]\n",
    "            m = max(m, prices[i] - dp[i])\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "        if not prices:return 0\n",
    "        dp = [0] * len(prices)\n",
    "        for i in range(1,len(prices)):\n",
    "            dp[i] = max(dp[i-1],prices[i] - min(prices[:i])) \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "        \n",
    "        size=len(prices)\n",
    "        if size==0:\n",
    "            return 0\n",
    "        dp=[0 for i in range(size)]\n",
    "        for i in range(1,size):\n",
    "            dp[i]=max(dp[i-1],prices[i]-min(prices[:i]))\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def bestTimingWithRecursion(self, prices: List[int]) -> int:\n",
    "        if len(prices) == 0:\n",
    "            return 0\n",
    "        res = []\n",
    "        maxProfit = -1\n",
    "        for i in prices:\n",
    "            heapq.heappush(res, i)\n",
    "            maxProfit = max(maxProfit, i-res[0])\n",
    "        return maxProfit\n",
    "\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "        if len(prices) <= 1:\n",
    "            return 0\n",
    "        min_val = int(1e5)\n",
    "        min_arr = []\n",
    "        for item in prices:\n",
    "            min_val = min(min_val, item)\n",
    "            min_arr.append(min_val)\n",
    "        \n",
    "        n = len(prices)\n",
    "        dp = [0]*(n+1)\n",
    "        for i in range(1, n+1):\n",
    "            dp[i] = max(dp[i-1], prices[i-1]-min_arr[i-1])\n",
    "        \n",
    "        return dp[-1]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int: \n",
    "        # if  prices:\n",
    "        #     return max(j - k for j,k in zip(prices, accumulate(prices,min)))\n",
    "        # else:\n",
    "        #     return 0\n",
    "\n",
    "\n",
    "\n",
    "        if len(prices)<=1: return 0\n",
    "        tmp = deepcopy(prices)\n",
    "        rs = []\n",
    "        for i in range(1,len(prices)):\n",
    "            if prices[i]>prices[i-1]:\n",
    "                prices[i]=prices[i-1]\n",
    "            else:\n",
    "                prices[i]=prices[i]\n",
    "        for i in range(len(tmp)):\n",
    "            rs.append(tmp[i]-prices[i])\n",
    "        return max(rs)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # left , right = 0 , 1\n",
    "        # maxprofit = 0\n",
    "        # while right < len(prices):\n",
    "        #     curProfit = prices[right] - prices[left]\n",
    "        #     #print(f'{prices[right]} - {prices[left]}----prices[{right}]-prices[{left}]')\n",
    "        #     if prices[left] < prices[right]:\n",
    "        #         maxprofit = max(curProfit,maxprofit)\n",
    "        #         #print(f'maxprofit={maxprofit}')\n",
    "        #     else:\n",
    "        #         left = right\n",
    "                \n",
    "\n",
    "        #     right += 1\n",
    "        # return maxprofit\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int: \n",
    "        # if  prices:\n",
    "        #     return max(j - k for j,k in zip(prices, accumulate(prices,min)))\n",
    "        # else:\n",
    "        #     return 0\n",
    "        if len(prices)<=1: return 0\n",
    "        tmp = deepcopy(prices)\n",
    "        rs = []\n",
    "        for i in range(1,len(prices)):\n",
    "            if prices[i]>prices[i-1]:\n",
    "                prices[i]=prices[i-1]\n",
    "            else:\n",
    "                prices[i]=prices[i]\n",
    "        # print(prices)\n",
    "        # print(tmp)\n",
    "        for i in range(len(tmp)):\n",
    "            rs.append(tmp[i]-prices[i])\n",
    "        # print(rs)\n",
    "        return max(rs)\n",
    "                \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "        def mergesplit(prices):\n",
    "            if len(prices) == 1:\n",
    "                return prices\n",
    "            mid = len(prices)//2\n",
    "            left = mergesplit(prices[:mid])\n",
    "            right = mergesplit(prices[mid:])\n",
    "            diff = right[0] - left[-1]\n",
    "            if diff > self.res:\n",
    "                self.res = diff\n",
    "            m, n = 0, 0\n",
    "            tmp = []\n",
    "            while m < len(left) and n < len(right):\n",
    "                if left[m] >= right[n]:\n",
    "                    tmp.append(left[m])\n",
    "                    m += 1\n",
    "                else:\n",
    "                    tmp.append(right[n])\n",
    "                    n += 1\n",
    "                    \n",
    "            if m < len(left):\n",
    "                tmp.extend(left[m:])\n",
    "            if n < len(right):\n",
    "                tmp.extend(right[n:])\n",
    "            # print(tmp)\n",
    "            return tmp\n",
    "\n",
    "\n",
    "        if prices == []:\n",
    "            return 0\n",
    "        mergesplit(prices)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int: \n",
    "        # if  prices:\n",
    "        #     return max(j - k for j,k in zip(prices, accumulate(prices,min)))\n",
    "        # else:\n",
    "        #     return 0\n",
    "        if len(prices)<=1: return 0\n",
    "        tmp = deepcopy(prices)\n",
    "        rs = []\n",
    "        for i in range(1,len(prices)):\n",
    "            if prices[i]>prices[i-1]:\n",
    "                prices[i]=prices[i-1]\n",
    "            else:\n",
    "                prices[i]=prices[i]\n",
    "        # print(prices)\n",
    "        # print(tmp)\n",
    "        for i in range(len(tmp)):\n",
    "            rs.append(tmp[i]-prices[i])\n",
    "        # print(rs)\n",
    "        return max(rs)\n",
    "                \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        dp = [[0 for i in range(n)], [0 for i in range(n)]]\n",
    "        dp[1][0] = -prices[0]\n",
    "        for i in range(1, n):\n",
    "            dp[0][i] = max(dp[0][i-1], prices[i] + dp[1][i-1])\n",
    "            dp[1][i] = max(dp[1][i-1], -prices[i])\n",
    "        return dp[0][-1]\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "        if len(prices)<=1:\n",
    "            return 0\n",
    "        \n",
    "        dp=[[0 for _ in range (len(prices))] for _ in range (2)]\n",
    "        #dp数组是2维的，0维代表不持有股票，1维代表持有股票。\n",
    "        dp[0][0]=-prices[0]\n",
    "        for i in range (1,len(prices)):\n",
    "            dp[0][i]=max(dp[0][i-1],-prices[i])\n",
    "            dp[1][i]=max(dp[0][i-1]+prices[i],dp[1][i-1])\n",
    "        print(dp)\n",
    "        return max(max(dp[1]),0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "        \n",
    "        def get_result(prices):\n",
    "            while len(prices) >= 2:\n",
    "                if prices[0] >= prices[1]:\n",
    "                    prices.pop(0)\n",
    "                elif prices[-1] <= prices[-2]:\n",
    "                    prices.pop()\n",
    "                else:\n",
    "                    break\n",
    "            if len(prices) < 2:\n",
    "                return 0\n",
    "            elif len(prices) == 2:\n",
    "                return prices[1] - prices[0]\n",
    "            elif prices[-1] <= prices[-2]:\n",
    "                return get_result(prices[:-1])\n",
    "            else:\n",
    "                return max(prices[-1] - min(prices[:-1]), get_result(prices[:-1]))\n",
    "\n",
    "        \n",
    "        return get_result(prices)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "        \n",
    "        def get_result(prices):\n",
    "            while len(prices) >= 2:\n",
    "                if prices[0] >= prices[1]:\n",
    "                    prices.pop(0)\n",
    "                elif prices[-1] <= prices[-2]:\n",
    "                    prices.pop()\n",
    "                else:\n",
    "                    break\n",
    "            if len(prices) < 2:\n",
    "                return 0\n",
    "            elif len(prices) == 2:\n",
    "                return prices[1] - prices[0]\n",
    "            else:\n",
    "                return max(prices[-1] - min(prices[:-1]), get_result(prices[:-1]))\n",
    "\n",
    "        \n",
    "        return get_result(prices)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "\n",
    "        cost, profit = float(\"+inf\"), 0\n",
    "\n",
    "        for price in prices:\n",
    "\n",
    "            cost = min(cost, price)\n",
    "\n",
    "            profit = max(profit, price - cost)\n",
    "\n",
    "        return profit\n",
    "'''\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "        \n",
    "        def get_result(prices):\n",
    "            while len(prices) >= 2:\n",
    "                if prices[0] >= prices[1]:\n",
    "                    prices.pop(0)\n",
    "                elif prices[-1] <= prices[-2]:\n",
    "                    prices.pop()\n",
    "                else:\n",
    "                    break\n",
    "            if len(prices) < 2:\n",
    "                return 0\n",
    "            elif len(prices) == 2:\n",
    "                return prices[1] - prices[0]\n",
    "            else:\n",
    "                return max(prices[-1] - min(prices[:-1]), get_result(prices[:-1]))\n",
    "\n",
    "        \n",
    "        return get_result(prices)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "        length = len(prices)\n",
    "        if length == 0:\n",
    "            return 0\n",
    "        dp = [[0] * 2 for _ in range(length)]\n",
    "        dp[0][0] = -prices[0]\n",
    "        dp[0][1] = 0\n",
    "        for i in range(1, length):\n",
    "            dp[i][0] = max(dp[i-1][0], -prices[i])\n",
    "            dp[i][1] = max(dp[i-1][1], prices[i] + dp[i-1][0])\n",
    "        return dp[-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices: List[int]) -> int:\n",
    "        if not prices: return 0\n",
    "        n = len(prices)\n",
    "        dp = [[0]*2 for _ in range(n)]\n",
    "        dp[0][1] = -prices[0]\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])\n",
    "            dp[i][1] = max(dp[i-1][1], -prices[i])\n",
    "        return dp[n-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- encoding: utf-8 -*-\n",
    "# @Author  :   Liang Hao \n",
    "# @Time    :   2023/11/10 15:56:26\n",
    "# @File    :   LCR_188.py\n",
    "# @Contact   :   lianghao@whu.edu.cn\n",
    "\n",
    "class Solution:\n",
    "    def bestTiming(self, prices):\n",
    "        n = len(prices)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        # flag-1表示购买\n",
    "        dp = [[0, 0] for _ in range(n)]\n",
    "        \n",
    "        # base case\n",
    "        dp[0][0] = 0\n",
    "        dp[0][1] = -prices[0]\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])\n",
    "            dp[i][1] = max(dp[i - 1][1], -prices[i])\n",
    "        \n",
    "        return dp[-1][0]\n",
    "        \n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
